//
//  143. 重排链表.swift
//  LeetCodeTrain
//
//  Created by rjb on 2021/9/4.
//  Copyright © 2021 rjb. All rights reserved.
//

import Foundation

class Solution143 {
    // 重排链表
    // 1. 找到链表中点
    // 2. 反转后半段链表
    // 3. 合并段链表
    func reorderList(_ head: ListNode?) {
        let mid = findMid(head)
        let midNext = mid?.next
        mid?.next = nil
        
        let head2 = reverseList(midNext)
        mergeList(one: head, two: head2)
    }
    func mergeList(one: ListNode?, two: ListNode?){
        guard let two = two else {
            return
        }
        var p1 = one
        var p2: ListNode? = two
        while p1 != nil {
            let p1Next = p1?.next
            let p2Next = p2?.next
           
            p1?.next = p2
            p2?.next = p1Next
            
            p1 = p1Next
            p2 = p2Next
        }
    }
    func findMid(_ head: ListNode?) -> ListNode? {
        var slow = head
        var fast = head
        while fast != nil {
            slow = slow?.next
            fast = fast?.next?.next
            if fast?.next?.next == nil {
                break
            }
        }
        return slow
    }
    func reverseList(_ head: ListNode?) -> ListNode? {
        var pre: ListNode?
        var cur = head
        while cur != nil {
            let next = cur?.next
            cur?.next = pre
            pre = cur
            cur = next
        }
        return pre
    }
    
    static func test() {
        let solution = Solution143()
        let node1 = ListNode(1)
        let node2 = ListNode(2)
       
        node1.next = node2
        
       
        
        solution.reorderList(node1)
    }
}
